package com.cty.twentyFourthDay;

import jdk.jshell.Snippet;

import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;

/*
给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表
*/
public class Q_34 {

    // 通过了 时间复杂度O(NLogN) 空间复杂度O(1)
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        for (int i = 1;i < lists.length;i++) {
           lists[0] = merge(lists[0],lists[i]);
        }
        return lists[0];
    }

    // 合并方法
    public ListNode merge(ListNode head1,ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy,temp1 = head1,temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val >= temp2.val) {
                temp.next = temp2;
                temp2 = temp2.next;
            } else {
                temp.next = temp1;
                temp1 = temp1.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if(temp2 != null) {
            temp.next = temp2;
        }
        return dummy.next;
    }

    // 力扣官方题解 方法一: 顺序合并 这种写法比主包的代码量少
    /*
    * 时间复杂度O(NlogN) 空间复杂度O(1)
    * */
    public ListNode mergeKLists2(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0;i < lists.length;i++) {
            ans = mergeTwoList(ans,lists[i]);
        }
        return ans;
    }

    //力扣官方题解 方法二:分治合并
    /*
     * 思路：将k个链表分成k/2 k/4。。。
     *      分开合并 最终会合成一个链表 直接返回即可
     *  时间复杂度 O(kn×logk) 空间复杂度O(logK) 因为递归要用到栈
     * */
    public ListNode mergeKLists3(ListNode[] lists) {
        return merge(lists,0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists,int l,int r) {
        if (l == r) {
            return lists[l];
        }
        // 说明已经合并完毕了
        if (l > r) {
            return null;
        }
        // 找到中间节点
        int mid = l + r >> 1;
        // 分成两个两个的合并
        return mergeTwoList(merge(lists,l,mid),merge(lists,mid + 1,r));
    }
    // 先实现一个内部来
    class Status implements Comparable<Status> {
        // 储存节点
        int val;
        // 储存节点值
        ListNode node;
        // 比较方法
        @Override
        public int compareTo(Status o) {
            return this.val - o.val;
        }

        public Status(int val, ListNode node) {
            this.val = val;
            this.node = node;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<>();
    //力扣官方题解 方法三:使用优先队列合并
    /*
    * 时间复杂度O(kn * Logk)
    * 空间复杂度O(K)
    * */
    public ListNode mergeKLists4(ListNode[] lists) {
        //使用for循环将所有的节点都包装成 Status实例对象存入优先队列
        for (ListNode head: lists) {
            if (head != null) {
                queue.offer(new Status(head.val, head));
            }
        }
        //创建一个哑节点
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!queue.isEmpty()) {
            Status status = queue.poll();
            tail.next = status.node;
            tail = tail.next;
            // 判断该节点该有没有后续节点
            if (status.node.next != null) {
                // 继续存入下一个节点
                queue.offer(new Status(status.node.next.val,status.node.next));
            }
        }
        return dummy.next;
    }


    // 合并两个链表
    public ListNode mergeTwoList(ListNode head1,ListNode head2) {
        if (head1 == null || head2 == null) {
            return head1 != null ? head1:head2;
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy,temp1 = head1,temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val > temp2.val) {
                tail.next = temp2;
                temp2 = temp2.next;
            } else {
                tail.next = temp1;
                temp1 = temp1.next;
            }
            tail = tail.next;
        }
        tail.next = temp1 != null ? temp1:temp2;
        return dummy.next;
    }


}
